package _back_tracking

import org.junit.Assert
import org.junit.Test

/**
 * 1863. 找出所有子集的异或总和再求和
 *
 * https://leetcode.cn/problems/sum-of-all-subset-xor-totals/description
 *
 * ```
 * 一个数组的 异或总和 定义为数组中所有元素按位 XOR 的结果；如果数组为 空 ，则异或总和为 0 。
 *
 * 例如，数组 [2,5,6] 的 异或总和 为 2 XOR 5 XOR 6 = 1 。
 * 给你一个数组 nums ，请你求出 nums 中每个 子集 的 异或总和 ，计算并返回这些值相加之 和 。
 *
 * 注意：在本题中，元素 相同 的不同子集应 多次 计数。
 *
 * 数组 a 是数组 b 的一个 子集 的前提条件是：从 b 删除几个（也可能不删除）元素能够得到 a 。
 *
 * 示例 1：
 * 输入：nums = [1,3]
 * 输出：6
 * 解释：[1,3] 共有 4 个子集：
 * - 空子集的异或总和是 0 。
 * - [1] 的异或总和为 1 。
 * - [3] 的异或总和为 3 。
 * - [1,3] 的异或总和为 1 XOR 3 = 2 。
 * 0 + 1 + 3 + 2 = 6
 *
 * 示例 2：
 * 输入：nums = [5,1,6]
 * 输出：28
 * 解释：[5,1,6] 共有 8 个子集：
 * - 空子集的异或总和是 0 。
 * - [5] 的异或总和为 5 。
 * - [1] 的异或总和为 1 。
 * - [6] 的异或总和为 6 。
 * - [5,1] 的异或总和为 5 XOR 1 = 4 。
 * - [5,6] 的异或总和为 5 XOR 6 = 3 。
 * - [1,6] 的异或总和为 1 XOR 6 = 7 。
 * - [5,1,6] 的异或总和为 5 XOR 1 XOR 6 = 2 。
 * 0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28
 *
 * 示例 3：
 * 输入：nums = [3,4,5,6,7,8]
 * 输出：480
 * 解释：每个子集的全部异或总和值之和为 480 。
 *
 * 示例 4：
 * 输入：nums = [1,1,1]
 * 输出：4
 * 提示：
 * 1 <= nums.length <= 12
 * 1 <= nums[i] <= 20
 * ```
 * 思路：![leetcode_1863.jpg](../../../../images/leetcode_1863.jpg)
 */

class leetcode_1863 {
    @Test
    fun test_1() {
        val actual = subsetXORSum(intArrayOf(1, 3))
        val expected = 6
        Assert.assertEquals(expected, actual)
    }

    @Test
    fun test_2() {
        val actual = subsetXORSum(intArrayOf(5, 1, 6))
        val expected = 28
        Assert.assertEquals(expected, actual)
    }

    @Test
    fun test_3() {
        val actual = subsetXORSum(intArrayOf(3, 4, 5, 6, 7, 8))
        val expected = 480
        Assert.assertEquals(expected, actual)
    }

    @Test
    fun test_4() {
        val actual = subsetXORSum(intArrayOf(1, 1, 1))
        val expected = 4
        Assert.assertEquals(expected, actual)
    }

    fun subsetXORSum(nums: IntArray): Int {
        /**
        回溯 - 子集
        思路：
        元素 相同 的不同子集应 多次 计数。 => 此题不需要树层去重
         先收集路径，再计算路径的异或值，再累加异或值
         */
        f(nums, 0, BooleanArray(nums.size))
        return sum
    }

    var sum: Int = 0
    var path: ArrayList<Int> = ArrayList()

    fun f(nums: IntArray, start: Int, used: BooleanArray) {
        // 1 确定函数参数以及返回值

        // 2 确定终止条件
        // 终止条件
        if(start > nums.size){
            return
        }
        // 收集结果
        var value : Int = 0
        for(n in path){
            value = value xor n
        }
        sum = sum + value
        println(path)

        // 3 确定循环方向
        for (i in start until nums.size) {
            // 处理节点
            // 不需要树层去重。因为 [1,1,1] 时，要得到[] 、[1] 、[1]、[1] 、[1, 1] 、[1, 1] 、[1, 1] 、[1, 1, 1]

            path.add(nums[i])
            // println("loop path:$path")

            // 递归
            f(nums, i + 1, used)

            // 回溯
            path.removeAt(path.size - 1)
            used[i] = false

            // 4 剪枝？
            // 5 去重？
        }
    }
}